/**
 * 动态规划
 * @param {number} n
 * @return {number}
 */
export var numSquares = function (n) {
  const dp = new Array(n + 1).fill(0)
  dp[1] = 1
  for (let i = 2; i <= n; i++) {
    let min = Number.MAX_VALUE
    let j = 1
    while (j * j <= i) {
      min = Math.min(min, dp[i - j * j])
      j++
    }
    dp[i] = min + 1
  }
  return dp[n]
}

/**
 * 官方的数学方法
  参考
  https://leetcode.cn/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode-solut-t99c/ 
 */
export var numSquares2 = function (n) {
  if (isPerfectSquare(n)) {
    return 1
  }
  if (checkAnswer4(n)) {
    return 4
  }
  for (let i = 1; i * i <= n; i++) {
    let j = n - i * i
    if (isPerfectSquare(j)) {
      return 2
    }
  }
  return 3
}

// 判断是否为完全平方数
const isPerfectSquare = x => {
  const y = Math.floor(Math.sqrt(x))
  return y * y == x
}

// 判断是否能表示为 4^k*(8m+7)
const checkAnswer4 = x => {
  while (x % 4 == 0) {
    x /= 4
  }
  return x % 8 == 7
}
